﻿using System;
using System.Linq;
using Algoritmia.Problems.GeneralizedCoinChange;
using Algoritmia.Utils;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.GeneralizedCoinChange.OnlyQuantityModeling
{
    public class RecursiveDynamicCoinChanger : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;

        public RecursiveDynamicCoinChanger(IList<int> values, IList<double> weights = null)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0,_n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            Func<int, double> L = null;
            L = q =>
                    {
                        if (q == 0)
                        {
                            return 0;
                        }
                        return Enumerable.Range(0, _n).Where(i => _values[i] <= q).Select(i => L(q - _values[i]) + _weights[i]).DefaultIfEmpty(double.PositiveInfinity).Min();
                    };
            return L(Q);
        }

        #endregion
    }
}
